Valid palindrome III

Time: O(N^2); Space: O(N); hard

Given a string s and an integer k, find out if the given string is a K-Palindrome or not.

A string is K-Palindrome if it can be transformed into a palindrome by removing at most k characters from it.

Example 1:

Input: s = “abcdeca”, k = 2

Output: True

Explanation:

  • Remove ‘b’ and ‘e’ characters.

Constraints:

  • 1 <= len(s) <= 1000

  • s has only lowercase English letters.

  • 1 <= k <= len(s)

1. Dynamic programming [O(N^2), O(N)]

[3]:

class Solution1(object):
    """
    Time: O(N^2)
    Space: O(N)
    """
    def isValidPalindrome(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: bool
        """
        if s == s[::-1]:  # optional, to optimize special case
            return True

        dp = [[1] * len(s) for _ in range(2)]

        for i in reversed(range(len(s))):
            for j in range(i+1, len(s)):
                if s[i] == s[j]:
                    dp[i%2][j] = 2 + dp[(i+1)%2][j-1] if i+1 <= j-1 else 2
                else:
                    dp[i%2][j] = max(dp[(i+1)%2][j], dp[i%2][j-1])

        return len(s) <= k + dp[0][-1]

[4]:

sol = Solution1()

s = "abcdeca"
k = 2
assert sol.isValidPalindrome(s, k) == True